\input{euler.tex}

\begin{document}

\problem[357]{Prime Generating Integers}

Consider the divisors of 30: 1, 2, 3, 5, 6, 10, 15, 30. It can be seen that for every divisor $d$ of 30, $d+30/d$ is prime. 

Find the sum of all positive integers $n$ not exceeding 100,000,000 such that for every divisor $d$ of $n$, $d+n/d$ is prime.

\solution

We use a brute force method. Note that if $n$ is such an integer, then $(1+n/1)$ must be prime, so $n$ must be equal to some prime $p$, minus one. This reduces the search space to all primes below $N$, which is in $\BigO(N/\ln{N})$.

For each candidate $n$, we just need to test all its divisors $d$ below $\sqrt{n}$. In addition, if $n / d$ is prime, then there are no more divisors between $d$ and $\sqrt{n}$ and we are done with this $n$. We maintain a prime table so that primality testing costs $\BigO(1)$ time. Hence, once we have generated a table of all primes below $N$, we can find the requested numbers in $\BigO(N\sqrt{N}/\ln N)$ time.

To generate the prime number table, we use the Sieve of Eratosthenes method, which runs in $\BigO(N \ln \ln N)$ time.

\answer

1739023853137

\complexity

Time complexity: $\BigO(N^{1.5}/\ln N)$

Space complexity: $\BigO(N)$

\reference

http://en.wikipedia.org/wiki/Sieve\_of\_Eratosthenes

\end{document} 